The present invention relates to a method of expressing and processing tree structured data of a computer system and, more particularly, to a processing method appropriate for pattern matching.
The matching technique of tree structured data will be inspected in the following. The "tree structured data" is herein termed the data which is constructed of nodes having their own values and an arbitrary number (including zero) of child nodes. However, it is assumed that the node relation contains no loop. It takes place in case the node relations (which will be called the "structure") are identical and in case the values of the individual nodes satisfy a coincidence judging condition that two tree structured data can be matched. The coincidence judging condition is termed a rule which is decided such that "a value "*" is deemed an arbitrary value whereas the others are deemed equal only to an identical value".
One example of the tree structured data is shown in FIG. 1. According to the above-specified coincidence judging condition, the tree structured data (a) of FIG. 1 cannot be pattern-matched with those (b) and (c) of FIG. 1. This is because the data (a) and (b) are different in structure whereas the data (a) and (c) are uncoincided at the values of the third nodes of the third levels. The data structures (a) and (d) of FIG. 1 can be matched.
In a representative method of expressing the physical data of the tree structured data according to the prior art, as shown in FIG. 2, a node having child nodes is expressed by an (n+1)) number of series cells, of which the first cell is stored with the value of the node itsel and the second and following cells are stored with pointers to the child node cells. Thus, the physical data expression of the tree structured data using the pointers will be called the "record type expression". FIG. 2 shows an example of the physical expression of the tree structured data of FIG. 1(a) using that method.
This expression method cannot be said to be appropriate for the aforementioned pattern matching processing. Since the nodes are coupled by the pointers, the nodes to be inspected must have their addresses temporarily avoided so that all of them may be sequentially inspected. Considering the inspection of propriety of matching two tree structured data by the breadth-first search, the addresses of all the nodes located at an equal depth have to be avoided when the individual depths of the tree structures are to be inspected. In other words, the record type expression of the prior art is inferior in the matching processing efficiency.